#ifndef __BWLIB_ALGORITHM_FAST_POWER_H__
#define __BWLIB_ALGORITHM_FAST_POWER_H__
#include "../config.h"
#include <stdexcept>

namespace bwlib
{
	/* @brief: 计算 a ^ b, 其中 b >= 0
	   @complexity: O(log b)
	   @param: a, b
	   @return: a ^ b
	   @concept: decltype(b) 需要有和 int 一样行为的 &、>>= 操作符 */
	template<typename Type, typename PowType>
	inline Type power(const Type& ta, const PowType& tb)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(tb < 0) throw std::runtime_error("b < 0 in power");
#endif
		Type a = ta;
		PowType b = tb;
		Type t(1);
		while(b != 0)
		{
			if((b & 1) != 0) 
				t *= a;
			a *= a;
			b >>= 1;
		}
		return __BWLIB_MOVE(t);
	}

	/* @brief: 计算 a ^ b, 其中 b >= 0
	   @complexity: O(log b)
	   @param: a, b
	   @return: a ^ b */
	template<typename Type, typename PowType>
	inline Type power_decay(Type a, PowType b)
	{
#ifdef __BWLIB_SAFER_CHECK
		if(b < 0) throw std::runtime_error("b < 0 in power");
#endif
		Type t(1);
		while(b != 0)
		{
			if(b % 2 != 0) 
				t *= a;
			a *= a;
			b /= 2;
		}
		return __BWLIB_MOVE(t);
	}
}

#endif
